package com.clstu.search;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * 演示差值查找算法的使用,----二分查找算法的优化版(也要求数组有序),
 * //可以更快的定位到要找的值的下标,使查找的数更小(注意,在数据比较连续的情况下能发挥最大速度)
 */
public class InsertValueSearch {
    public static int count = 0;
    public static void main(String[] args) {
//        HashMap<String,HashMap<String,Integer>> set = new HashMap<>();
        //测试
        int[] arr = new int[100];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=i+1;
        }
        System.out.println(insertValueSearch2(arr,0,arr.length-1,55));
    }

    //编写方法实现差值查找算法(没找到返回-1)
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        System.out.println("插值查找次数:"+(++count));
        //思路分析:
        //跟二分法一样的过程,
        // 区别在于mid的确定,(left+right)/2 -----(变化为)---> left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left])
        //如果不用查找
        if(left>right || findVal < arr[left] || findVal > arr[right] ){
            return -1;
        }
        //自适应确定mid
        int mid = left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        //分如下3种情况返回
        if(findVal>arr[mid]){
            return insertValueSearch(arr,mid+1,right,findVal);
        }
        if (findVal<arr[mid]){
            return insertValueSearch(arr,left,mid-1,findVal);
        }
        return mid;
    }

    //编写查找查找算法升级版,可以返回多个下标放在ArrayList种,
    public static List<Integer> insertValueSearch2(int[] arr,int left,int right,int findVal){
        System.out.println("插值查找次数:"+(++count));
        //如果不用查找
        if(left>right || findVal> arr[right] || findVal < arr[left]){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> resList = new ArrayList<>();
        //自适应确定mid
        int mid = left + (right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        //分如下3种情况返回
        if(findVal>arr[mid]){
            return insertValueSearch2(arr,mid+1,right,findVal);
        }
        if(findVal<arr[mid]){
            return insertValueSearch2(arr,left,mid-1,findVal);
        }
        resList.add(mid);
        //左扫描
        for(int i = mid-1; i>=left && arr[i]==findVal ;i--){
            resList.add(i);
        }
        //右扫描
        for (int i = mid+1; i <= right && arr[i]==findVal ; i++) {
            resList.add(i);
        }
        return resList;
    }
}
